package com.rfs.suanfa;

public class 寻找数组中的重复数 {
    public static void main(String[] args) throws InterruptedException {
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 5};
        int duplicate = findDuplicate2(nums);
        System.out.println(duplicate);
    }

    public static int findDuplicate(int[] nums) {
        int[] counter = new int[nums.length];// 计数器法 默认都是[0,0,0,0,0]
        for (int num : nums) {
            if (counter[num] == 1) { //如果第num位置已经被+1 说明这个是重复的
                return num;
            }
            counter[num]++;
            //第一轮 [0,1,0,0,0]
            //第二轮 [0,1,0,1,0]
            //第三轮 [0,1,0,1,1]
        }
        return -1;
    }

    /**
     * @author: rfs
     * @create: 2022/4/24
     * @description: 快慢指针法
     **/
    public static int findDuplicate2(int[] nums) {
        int fast = nums[nums[0]];
        int slow=nums[0];
        while (fast!=slow) {
            fast=nums[nums[fast]];
            slow=nums[slow];
        }
        int finder=0;
        while (slow!=finder) {
            finder = nums[finder];
            slow = nums[slow];
        }
        return slow;
    }
}
